package com.gitee.alg.sort

/**
 * Project Name: alg
 * Des: 堆排序
 * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，
 * 并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
 * 堆排序可以说是一种利用堆的概念来排序的选择排序。
 * 1. 创建一个堆 H[0……n-1]；
 * 2. 把堆首（最大值）和堆尾互换；
 * 3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
 * 4. 重复步骤 2，直到堆的尺寸为 1。
 *
 * Package:com.gitee.alg.sort
 * @author Arlo Sun
 * @date 2021/4/27 - 13:03
 */
class HeapSort<T : Comparable<T>>(override val compare: (T, T) -> Boolean) : ArraySort<T> {

    override fun sort(array: Array<T>, ascend: Boolean): Array<T> {

        val length = array.size

        //执行完后即根节点已调整为最大值
        buildMaxHeap(array, length)

        for (i in length - 1 downTo 1) {
            array.swap(0, i)
            heapify(array, i, 0)
        }

        return array
    }

    //创建最大堆 ，即遍历整个树，使树合规
    private fun buildMaxHeap(array: Array<T>, length: Int) {

        //  以根节点为1,左子节点0，右子节点为1，给每个节点赋上坐标，
        //  最后一个节点的坐标即为,整个树的节点总和或者说是数组长度
        //  直接定位到最后一个非叶子节点，即地址最远的父节点   向前遍历即可完成树的遍历
        //  所以下面的操作更符合语义 。。。
        val half = length shr 1 - 1

        for (i in half downTo 0) {
            heapify(array, length, i)
        }

    }

    private fun heapify(array: Array<T>, length: Int, index: Int) {
        /*就这里费劲 li ri 是index对应的元素的子节点元素  因为堆是近似完全二叉树
        * 像是二进制的基数树，长度对应的是树的最后一个节点的坐标
        * 树的节点跟数组里面是一层一层映射下来的
        * 1层 1个(根)  2层 2个 3层 4个 这样对应的  所以  每个父节点对应的子节点 是
        *  (index + 1) << 1 - 1 和 (index + 1) << 1 + 1 - 1
        *  即 index*2 +1 和 index *2 + 2   */
        val li = 2 * index + 1
        val ri = 2 * index + 2
        var parentIndex = index
        if (li < length && compare(array[li], array[parentIndex])) {
            parentIndex = li
        }

        if (ri < length && compare(array[ri], array[parentIndex])) {
            parentIndex = ri
        }

        if (parentIndex != index) {
            //调整位置的时候需要的递归的调整对应子节点的位置
            array.swap(parentIndex, index)
            heapify(array, length, parentIndex)
        }
    }
}
